Handling special cases like self-loops and multiple edges between the same nodes.

  • An undirected self-loop at a vertex adds 2 to its degree, while a directed loop adds 1 to both its in-degree and out-degree. This is a common point of confusion.
  • Parallel edges require data structures that can store multiple instances or counts, like a list or a Counter, instead of a simple set which only stores unique neighbors.
Python: Handling Multiplicity
from collections import Counter, defaultdict
# multigraph adjacency with edge multiplicities
adj_multi = defaultdict(Counter)
def add_parallel(u,v):
    adj_multi[u][v] += 1
    adj_multi[v][u] += 1

def add_loop(u):
    # An undirected self-loop adds 2 to the degree
    adj_multi[u][u] += 2

add_parallel("A","B"); add_parallel("A","B")
add_loop("A")
adj_multi["A"]["A"]  # == 2